perm filename QLISP.MSG[P,LES] blob sn#851477 filedate 1988-01-07 generic text, type C, neo UTF8
COMMENT āŠ—   VALID 00023 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002		APPENDIX D -- Budget for three years beginning 1 June 1985.
C00007 00003	    Capital equipment
C00009 00004					Lucid
C00013 00005	Qlisp first task
C00016 00006	---------------------------------------------------------------------------
C00020 00007	Introduction
C00032 00008	Tools for parallel symbolic programming
C00036 00009	Facilities and Support
C00040 00010	Collaboration and connections with other projects 
C00043 00011	Parallel Algorithms for Algebraic Manipulation
C00051 00012					APPENDIX A
C00073 00013	     APPENDIX D -- Budget for eighteen months beginning 1 December 1985.
C00078 00014				U.C. Berkeley Budget
C00090 00015					Lucid
C00094 00016	     APPENDIX D -- Budget for eighteen months beginning 1 December 1985.
C00098 00017	    Capital equipment
C00100 00018					Lucid
C00103 00019	Qlisp revised budget
C00108 00020	Qlisp Task Description
C00119 00021	Qlisp Task
C00131 00022	BUDGET (18 months)
C00136 00023	                                Lucid
C00141 ENDMK
CāŠ—;
	APPENDIX D -- Budget for three years beginning 1 June 1985.

		Stanford University proposal to DARPA
				for
		    Qlisp on parallel processors

				Budget for year	   1          2          3
				    beginning	6-1-85     6-1-86     6-1-87
Personnel
    Prof. John McCarthy, Principal Investigator	19,713     19,713     19,713
      (15% acad. yr., 50% summer)

    Lester Earnest, Senior Res. Assoc. (100%)	67,500     67,500     67,500

    Carolyn Talcott*, Research Associate (100%)	43,000     43,000     43,000

    -----, Research Associate (100%)		41,000     41,000     41,000

    -----, Computer Systems Analyst (100%)	40,000     40,000     40,000

    -----, Computer Technician (25%)		 8,000	    8,000      8,000

    Ross Casley, Student Research Assistant	12,600     12,600     12,600
		(50% acad. yr., 100% summer)
    Ian Mason, Student Research Assistant	12,600     12,600     12,600
		(50% acad. yr., 100% summer)
    -----, Student Research Assistant			   12,600     12,600
		(50% acad. yr., 100% summer)
    -----, Student Research Assistant			   12,600     12,600
		(50% acad. yr., 100% summer)
    -----, Secretary (50% time)			10,440     10,440     10,440
					       -------    -------    -------
	Salary subtotals		       254,853    280,053    280,053

	Allowance for salary increases (9%/yr)	     0     25,205     52,678
					       -------    -------    -------
	Salary totals			       254,853    305,258    332,731

	Staff benefits (24.1% initially,	63,892     77,993     86,676
	  25.4% beg. 9/1/85, 25.6% beg. 9/1/86,
	  26.2% beg. 9/1/87)
    Consultants (10 days/yr. @ $500)		 5,000      5,000      5,000

    Travel (8 East Coast trips/yr. @ $1000,	15,000     15,300     16,300
	14 Western trips @ $500, adjusted for
	inflation)
    Computer maintenance 			73,819	   73,819     73,819
	(based on Sequent Computer)
    Computer time costs (based on 1984 usage	36,000     48,000     48,000
	of SAIL computer usage by principals)
    Other direct costs				22,600     26,900     28,600
					       -------    -------    -------
	Subtotal			       471,164    552,270    591,126

  * To be appointed.
    Capital equipment
      2 multiprocessor computer systems
	(e.g. Sequent Balance 8000 systems)    615,160
      Ethernet workstation cluster (8 term.)    24,000
      Ethernet page printer			11,937
      Additional workstations & peripherals		   12,000      8,000

    Lucid subcontract			       518,000	  408,300    234,600

    U.C. Berkeley subcontract		       182,000    215,300    226,700

    Indirect costs (69% of direct costs,       359,603    381,066    407,877
      excluding all capital equipment and
      subcontract amounts over $25,000)	       -------    -------    -------

    Total by year			     2,181,864  1,568,936  1,468,303
					       -------    -------    -------
    Project cumulative total		     2,181,864  3,750,800  5,219,103

				Lucid
			Project Cost Estimate
			      ($000's)

				Year 1	   Year 2    Year 3    Total

Direct Labor (Sch. A)		 109.2	    113.4      62.3    284.9

Salary Related Expense @19.8%     21.6       22.5      12.3     56.4
				------------------------------------	
Salary Expense			 130.8      135.9      74.6    341.3

Overhead @148%			 193.6      201.1     110.4    505.1

Other Direct Project Costs 
(Sch. B)			 126.0       18.0      19.0    163.0
				------------------------------------
			  	 450.4      355.0     204.0   1009.4

Fee @15%			  67.6       53.3      30.6    151.5
				------------------------------------
Total Project Cost		 518.0	    408.3     234.6   1160.9

Notes:
1.  Project cost assumes 1 Sequent machine provided to Lucid at no additional 
cost located at Lucid facilities for duration of project.

2.  Salary Related Expense and overhead are provisional rates based on FY86
(year end June 30) business plan projections.

3.  Direct Labor rates escalated at 10% per year.




			Schedule A
		       Direct Labor
			($000's)

				Year 1	   Year 2    Year 3    

Principal Investigator
	man-months		   3	      2		1
  	rate per month		   6.0        6.6       7.3
	total dollars		  18.0	     13.2       7.3

Senior Scientist
	man-months		  12	     12	      12
	rate per month		   5.0        5.5      6.1
	total dollars		  60.0	     66.0     36.1

Scientist
	man-months		   6	      6	       3
	rate per month		   4.2	      4.6      5.1
	total dollars		  25.2	     27.6     15.3

Technician
	man-months		   2	      2	       1
	rate per month		   3.0	      3.3      3.6
	total dollars		   6.0	      6.6      3.6

Total Man-Months		  23	     22	      10

Total Dollars			 109.2	    113.4     62.3


				Schedule B
			Other Direct Project Costs
				($000's)


				Year 1	   Year 2    Year 3    Total

Computer Equipment & Supplies      
	Symbolics 3670		   108	  
	Supplies @ 3K/yr	     3	        3         3        9
	Stanford Communication	     2          1         1        4

Travel & Subsistence
	Air		
	2 trips to Washington, D.C. @1.5 ea.
	1 trip to National Conference @1.5
	4 trips to East Coast, technical workshop @1.5 ea.

	Local travel @.5/yr	    11	      12	13	  36
	 escalate @10%/yr

Printing and Reproduction @2K/yr     2	       2	 2	   6
       				 ------------------------------------	
Total			           126	      18        19       163

Qlisp first task
Steve and John:

Here is a slightly revised version of the Qlisp proposal, with the initial
implementation effort broken out as a task to be performed over an 18
month period.  As we discussed, this task could be assigned to the
existing contract (N00039-84-C-0211) for advanced R&D in computer science.
The proposed period of performance (12/1/85 through 5/31/87) is chosen to
begin as early as seems practical and to extend to the current termination
date of the cited contract.

As revised, this proposal presents the whole work plan but requests
funding just for the initial implementation phase.  Funding to support
applications testing and tuning tasks is to be requested subsequently.
Relative to the earlier submission, we have figured out a way to save
some capital equipment money: instead of getting one machine for Stanford
and one for Lucid, we plan to install a microwave link between Lucid's
new quarters (they will move shortly) and the Stanford ethernet environment,
which is in turn tied to ARPAnet.  We expect that this will provide adequate
computational support for the three main parties to this proposal for at
least the period of this task.

We stand ready to crank this through the Stanford mill at the earliest sign
of encouragement.  Please let me know if you see any problems.

Best Regards,
		Les Earnest

---------------------------------------------------------------------------

			STANFORD UNIVERSITY

			    Proposal to

	    Defense Advanced Research Projects Agency

				on

		   Qlisp for Parallel Processors

	   John McCarthy, Professor of Computer Science
			Principal Investigator

Task Summary

An extension of Common Lisp for parallel processing, called Qlisp, is
planned to use queue-based multi-processing.  It has the following
features.

o   Each processor can address the whole of memory, and a processor may
    execute programs anywhere in memory on data located anywhere in memory.

o   The programmer indicates when parallelism is possible by using parallel
    constructions in the source language, which is an extension of Lisp.

o   When a program comes to a statement allowing parallelism and decides
    (according to the computed value of an allow-parallelism parameter
    in the statement) that parallelism is to be invoked, it adds a
    collection of tasks to a queue and starts on the first.

o   When a processor completes a task it goes to the queue for its next task.

Basing parallelism on run-time queues means that a program isn't written
or compiled for any specific number of processors.  The number available
can even change during the course of a computation.  Tasks need not be of
similar length, because a processor finishing a short task merely takes
another from the queue.

This project will involve a collaboration between Stanford University,
University of California at Berkeley and Lucid, Inc.  An initial task of
18 months duration will produce a functioning Qlisp system, documentation
and debugging tools at a cost of $2.6 million.

This is proposed as a step toward the longer range goal of demonstrating
symbolic computation in a parallel computing system.  The follow-on task,
to be proposed for funding later, will apply, evaluate, and tune the Qlisp
system on demonstration tasks in symbolic computation.  For comprehensibility,
this proposal describes both tasks.

Introduction

This is a proposal for research in implementing and demonstrating
applications of an extension of Lisp for parallel processing called Qlisp.
The scheme under discussion was called ``Qlambda'' in Gabriel and
McCarthy (1984).  An extension of that paper is included as Appendix B.
The name ``Qlambda'' was used instead of ``Qlisp'' because there had been
an earlier system called Qlisp developed by Earl Sacerdoti.  In a recent
discussion, Dr. Sacerdoti indicated that the earlier Qlisp has been out of
use long enough that he thinks the likelihood of confusion arising from
reuse of the name is small.  Therefore we are adopting the preferred name
of ``Qlisp.''

Qlisp allows the programmer to specify tasks that may be performed in
parallel by creating queues of tasks.  The project involves acquiring a
parallel processor, developing Qlisp for it, developing test applications
for it (algorithms for algebraic mathematics comparable to those of
Macsyma), and testing the performance of the applications on substantial
symbolic computation tasks.

The project will be carried out with both formal and informal
collaboration among several groups.  The principal investigator for the
overall project will be Professor John McCarthy.  The Qlisp implementation
will be done under subcontract to Lucid Inc.  The design and
implementation of Qlisp will be supervised by Richard P. Gabriel of Lucid.
The Macsyma application will be developed in collaboration with Professor
Richard Fateman of the University of California at Berkeley.  Separate
proposals for the Lucid subcontract and Fateman's contribution to the
Macsyma application are attached.  Development of parallel programming
tools and programs for testing applications will be supervised by Carolyn
Talcott.  We expect to interact substantially with other symbolic parallel
processing projects at Stanford and Berkeley.  This interaction is
outlined below.  The parallel facility and Qlisp will be available on the
ARPAnet for others to try out.

It is generally agreed that the main hope for large increases in computer
speed, whether for numerical work or symbolic computation as in artificial
intelligence, lies in massive parallelism.  Projects are being undertaken
that will involve hundreds or even thousands of processors.  However,
no one has yet demonstrated the ability to make general purpose use of
even two processors on symbolic computation for a single problem.  Indeed
even numerical computation on parallel processors has been difficult, and
there are no general purpose computation systems that make good use of
parallel processors in spite of more than twenty years of work.
Therefore, it is important to explore a variety of approaches to getting
good performance from parallel processors on a variety of problems.

Our approach is queue-based multi-processing.  It has the following
features.

1. Each processor can address the whole of memory, and a processor
may execute programs anywhere in memory on data located anywhere in memory.
This makes difficulty for the hardware designer, but we are running scared
on programming, and we cannot necessarily accept the forms of parallelism
that hardware people find most convenient to implement.

2. The programmer indicates when parallelism is possible by using
parallel constructions in the source language, which is an extension of
Lisp.  See Gabriel and McCarthy 1984, an extension of which is included as
Appendix B, for a description of this language called Qlisp.

3. When a program comes to a statement allowing parallelism and decides
(according to the computed value of an allow-parallelism parameter in the
statement) that parallelism is to be invoked, it adds a collection of
tasks to a queue and starts on the first.  When a processor completes a
task it goes to the queue for its next task.  It may execute some queue
management code to decide what to do next.

4. Basing parallelism on run-time queues means that a program isn't
written or compiled for any specific number of processors.  The number
available can even change during the course of a computation.  Tasks need
not be of similar length, because a processor finishing a short task merely
takes another from the queue.

5. While Qlisp is more fully described in the paper, we mention
just the statement  QLET here.  Its form is

		QLET allow ((x1 arg1))
				. . .
				. . .
				. . .
			((xn argn)).body).

The parameter "allow" is evaluated first.  If its value is (), i.e. false,
parallelism is not allowed and the QLET statement behaves like an ordinary
Common Lisp LET.  If the value is something else and not EAGER, then a
queue of tasks is set up to evaluate arg1 ... argn, and the processor
takes a task from the queue.  If the value is EAGER, the processor sets up
the queue and immediately starts on evaluating body, suspending if it
comes to a variable whose value has not yet been computed.

The point of exhibiting QLET here is that the parameter allow is evaluated
to determine whether parallelism is allowed.  Because Lisp (and symbolic
computation generally) is highly recursive, it can generate a large number
of parallel tasks.  However, we need only enough parallelism to keep our
processors busy.  Therefore, the expression allow should often be false.
Qlisp is designed according to the idea that it is necessary to limit
parallelism as well as to instigate it.

	We believe that it is necessary to follow through on the
development and implementation of Qlisp by trying it out on
substantial applications.  These trials will most likely lead to
improvements in Qlisp and in the parallel processing hardware.
They may also determine whether it is possible to relax the requirement
that all memory be equally accessible to all processors, since
the hardware people find this expensive to implement.

        There are two kinds of problems that to which parallelism
can be applied.  In one case the goal is make what you already have run
faster.  This improves interaction with the computer and allows larger
problems to be addressed.  In the second case, speed is of the essence.
Part of of the algorithm is devoted to insuring speed and some sort of
``real time'' behavior.  For example, a process may want to time out or
use some default value if a subprocess does not reply within a given time
limit.  Qlisp primitives directly address problems of the first sort.
Additional primitives may be needed for the real-time applications.  For
this a number of questions will need to be answered.  Can the additional
primitives can be coded in Qlisp?  Can they be coded easily and
efficiently?

	We have chosen a Macsyma-like system as an initial target application.  This is an application of the first sort.  
Our reasons for choosing this rather than an AI application are the following.

1. Macsyma and similar systems like REDUCE and SMP use a wide variety
of algorithms each with its own inner loop and each of which presents its
own problems of parallelism.

2. When a sufficient number of features have been implemented,
we can compare performance with algebraic computation systems running
on single processors.

3. The task is definite enough to be readily defined and supervised.
Some of our group are eager to undertake it.

We are also thinking about possible AI applications, e.g. to problem solving,
but are not ready to decide on one.  

Tools for parallel symbolic programming

The work proposed here involves an entirely new style of programming and
will require the development of new methods and tools to support the
programming activity.  This development will be carried out in parallel
with and in support of the chosen application.

    Algorithm design

Part of the development of parallel lisp involves discovering what
primitives are needed to carry out various tasks.  This involves
classifying problems as to the sort of parallelism required and the design
of control structures appropriate for the various classifications.  Two
well known classifications are AND versus OR parallelism and asynchronous
tasks with occasional interactions versus synchronous tasks operating on a
shared data structure.  Somewhat newer ideas include pipelines and other
geometric structures that make it easy to visualize the interactions among
a set of processes.  These latter ideas are discussed in
Appendix B.  In some cases successful use of parallelism will
require design of data structures with information making them suited to
parallel processing.

    Methods for debugging.

Traditional Lisp debugging methods such as stepping and tracing are not
going to be adequate for debugging Qlisp programs.  Programmers will
need to learn where to look for bugs and to devise methods for identifying
meaningful checkpoints.  We will build tools for for monitoring the
progress of a set of processes working on a problem.  We will also work on
informal methods of specification and reasoning about Qlisp programs as
aids to the process of program development and testing.

    Benchmarks and measures of success.

We will design benchmarks for testing parallel lisps and for comparing
the relative efficiency of parallel and sequential algorithms.  We will
also develop tools for measuring factors such as degree of parallelism
achieved, queue management overhead, and memory contention.  Some
measuring tools have already been developed by Gabriel in a sophisticated
system for simulating execution of Qlisp programs.  This system was used
in initial experiments testing Qlisp primitives.

Facilities and Support

In order to develop and test the scheme outlined above, it will be
necessary to have access to machines that execute multiple instruction
streams concurrently.  There are a number of novel machines with parallel
architectures in various stages of development currently and it is not
clear which approaches will emerge as the most cost/effective in the long
run.

In view of this, we propose to acquire a system that is commercially
available and relatively mature, both in hardware and in operating system,
so that our parallel software development efforts can proceed with
relatively little impairment from developmental bugs in the basic hardware
and operating system.  It will not be necessary to acquire a functionaly
complete computer system, including all necessary peripherals---existing
computer facilities at Stanford, including SAIL and SCORE computers, can
provide some of these functions.

We propose that a substantial portion of the developmental effort be
undertaken by Lucid under a subcontract, as discussed below.  [We
recommend that a sole source contract be negotiated with Lucid, Inc.
because Richard Gabriel, who is a founder and President of Lucid, is the
co-inventor of Qlisp.]

For the implementation task, we plan to acquire one multiprocessor system
and make it accessible to all participants via communication links.
Toward this end, we have budgeted for a microwave link between Lucid's
offices and the Stanford campus ethernet, which will also provide linkage
to ARPAnet.  For the follow-on application and testing task it may be
necessary to acquire an additional system.

We have carefully examined a number of possible system configurations from
a number of prospective suppliers, including BBN, Denelcor, Encore,
Sequent, Symbolics, and Synapse.  It appears that several machines that
could meet our needs are available.  We propose to choose the most
suitable system available at the time funding becomes available.  The
budget has been formulated based on the Sequent Balance 8000, which is one
of the machines that appears suitable, but we are leaving the final
selection open for now.

Collaboration and connections with other projects 

There are several other groups working on aspects of parallel symbolic
computation with whom collaboration will have mutual benefit.  Two
particular projects are:

  (HPP-AA) The advanced architectures group from the heuristic programming
    project as Stanford (Feigenbaum, Nii) 

  (SPUR) The parallel Lisp on a RISC machine project at UC Berkeley

Some obvious benefits come from the opportunity to share ideas
on real parallel programming techiques and the problems to be solved.
In addition there are some specific benefits.

The advanced architecture project will benefit from having a parallel
Lisp running on real machine rather than using simulations.  They are
working on parallel implementation of the blackboard model for expert
systems which will provide an additional substantial application with
emphasis on AI methods and asynchronous interactions.  This will provide
input on additional primitives needed in Qlisp and programs for testing
implementation of these primitives.  There is already some on-going
collaboration with regard to designing parallel control structures and
testing them in a simulation of Qlisp.

The SPUR project will get additional applications for testing their
primitives including benchmarks designed for Qlisp and for the Macsyma
application.  There can be mutual input on parallel primitives at
software, operating system and hardware levels.  In a later stages,
assuming good progress on the part of both projects, it will be reasonable
to implement Qlisp on the SPUR machine.  Collaboration with the SPUR group
will be facilitated by our collaboration with Fateman on the Macsyma
application.

Parallel Algorithms for Algebraic Manipulation

[This part of the project will be done by Richard Fateman and his group at
U.C. Berkeley.]

We propose to design, implement, and test algorithms in Qlisp
for the purpose of
(i) validating the Qlisp primitives and compiler design, 
(ii) demonstrating realistic applications where the high speed provided
    by multi-processing can be put to good use.

Our areas of interest include algebraic manipulation programs (typified by
Macsyma) and other symbolic mathematical computations.  These programs
have benefitted in the past by advances in computer hardware (large
address spaces, cheap memory, high speed), and should lead in the use of
non-numeric parallel processing.  While past uses have been primarily in
applied mathematics and engineering, and occasionally in theorem proving,
number theory, and compiler theory, it appears that there is an increasing
interest in symbolic mathematics capabilities for computer-aided design
and AI applications.

Since important algorithms have already been refined over the past dozen
years or more in serial implementations, we have an opportunity to make
realistic judgments regarding the advantages of parallel programs.

While it is not possible to identify all opportunities for parallelism
at the outset, we can suggest the following directions:

1. Exploit obvious cases of traditional parallel algorithms, e.g. FFT for
multiplying polynomials. The FFT in symbolic manipulation is done in a
finite computation structure (not complex floating-point numbers), but is
otherwise similar to the usual FFT.

2. Use multiple processors to multiply two polynomials by divide and
conquer, or by farming out partial products. Combining partial products by
addition is tricky, and hash-coding by exponents (to coalesce
corresponding coefficients) may provide a neat application.

3. Examine multiple-homomorphism (mod Q) algorithms such as polynomial
GCD, trying to do several moduli at the same time, for example.  The GCD
problem has been well studied, but GCD computation can nevertheless occupy
large amounts of time in certain common manipulations (e.g. addition of
rational functions.).

4. In factoring polynomials over the integers, several moduli generally
used in a first step (factoring polynomials over several finite fields).
This could clearly be done in parallel, although this is not usually the
expensive part of the algorithm.  Combinatorial matching of factors of
different degrees is much more time-consuming; an extravagant number of
moduli can sometimes simplify the matching.  Alternatively, the matching
process could be done in parallel.

5. Linear algebra algorithms: some classical calculations have been shown
to run relatively faster with symbolic entries, using methods that are
highly appropriate for parallel calculation, even though the same methods
are terrible for floating-point.  The best known example is the
computation of matrix determinants for which expansion by minors is
believed superior to Gaussian elimination.  Actually implementing this on
a multiprocessor should make good use of division of labor.

6. General simplification of expressions represented in trees: to simplify
f(a,b,c,...) one simplifies a,b,c,...  to a', b', c', ...
and then simplifies f(a', b' , ...).
Two improvements are obvious: simplify the arguments in parallel;
sort the arguments by a parallel sort  (e.g. if f is +, or some
other commutative operation).

7. Pattern matching drives some algorithms (e.g. indefinite integration).
Heuristic pattern matching with back-tracking may become more practical
with parallel processing, and should perhaps be revived as a more
fundamental control structure in some of the problem-solving programs.

8. Parallel garbage collection of cons cells or other (much larger) data
objects constructed by algebraic manipulation might be worth exploring.

9. We have experimented with frame-based objects with multiple
representations: we could compute simultaneously with different forms
(e.g. 
polynomials:[expanded, recursive, factored],
curves:[parametric, point-set, constraints],
matrices:[dense, \break sparse, factored])

    Resources needed:

We assume there will be an implementation effort at Stanford which
will produce a Qlisp simulation and an actual Qlisp implementation
on a parallel architecture machine.

The simulation would be available for use on hardware already in place
at UCB (including VAX, SUN, Symbolics, or Xerox), but the actual
parallel processor would be at Stanford.  Substantial computing would
be required at UCB for program preparation, testing, communication,
etc.

    Reference:

Gabriel, Richard and  John McCarthy (1984):
``Queue-based Multi-processing Lisp''
in "Proceedings of the 1984 ACM Symposium on Lisp and Functional Programming",
August 1984.

				APPENDIX A

[A contract to implement Qlisp will be negotiated on the basis of the
following proposal from Richard Gabriel of Lucid, Inc.]

Proposal to Implement Qlisp.

    Introduction

The purpose of the work proposed here is to produce a Qlisp
which runs on commercially available multiprocessor hardware.
The implementation will be a native-code Qlisp---there will be
a compiler that produces code that the processors in a multiprocessor
execute directly. This is contrasted with a compiler that produces
an abstract machine language that an interpreter running on the
multiprocessor interprets.

This part of the proposal is in several sections. The first describes the
technical issues, the second describes Lucid's ability to perform the
work, and the last section is an accounting of the anticipated level of
work to accomplish the goals as well as a set of milestones.

    Implementing Qlisp

Qlisp is a dialect of Lisp with extensions for multiprocessing. 
The extensions require the implementation of locking primitives,
interprocessor interrupts, a simple queue-based scheduler for
the multiprocessor, process creation, process killing, and process
protection.

For each of these operations, the implementation may need to rely on
facilities provided by either the hardware or the operating system. Lucid
is prepared to do some operating system work in the form of modifications
to existing software to accomodate these needs, but Lucid shall not
be held in breech of contract if forces beyond its control prevent 
such modifications by Lucid. Furthermore, if the operating system and
hardware prove to be inadequate for implementing Qlisp, and if there
is no recourse available from the hardware supplier, Lucid shall not
be held in breech of contract for failure to develop the needed software.

    Shared Memory/Shared Address Space

Implementing Qlisp requires a multiprocessor in which all of the processes
can operate on a shared heap. This does not require that the machine has
a uniformly shared memory, but it does require a shared address space.
A multiprocesor with some local non-shared address space memory might
provide good performance if code is executed from that local memory.
However, in this case there must be a means to `page' code from the global
memory into the local memories as needed, or else each local memory must
be large enough to hold all of the program code.

    The Global Queue

Qlisp requires that there be globally accessible queue of runnable
Qlisp processes, and that this queue be user-modifiable using
very strict functions. The user is able to place processes in the
queue using QLET and by invoking process closures created using
QLAMBDA. Also, using CATCH/QCATCH/THROW the user is able to remove
processes.

The original formulation of Qlisp required that the processors would
timeshare among processes so that every process that was actually runnable
would make some progress, though the progress might be minimal. On several
candidate machines this ability might be too costly (in terms of
efficiency) to provide.  In this event Lucid will explore the possibility
of restricting the creation of new processes so that the number of
processes created will not exceed the number of processors available.

    Function Calling

Qlisp requires a heavy use of closures. In order to minimize the cost of
creating and passing around closures, Qlisp will not use a stack for control.
Rather it will use what is called a `Big Bag of Frames' (BBOF).  The idea is
that each function will manipulate a heap-allocated frame rather than a
stack allocated frame. This little block of storage, along with pointers
from each one to the parent frame and other closure frames, will make
closure implementation simple. Also, the process structures will simply be
a pair, one pointing to a frame and another to a code vector.

There will be a performance penalty for non-parallel Lisp code using this
scheme, but by pre-allocating a number of various sizes of frames, perhaps
using a buddy-block scheme, this penalty can be reduced. Some preliminary
experiments show that the function-calling performance degradation can
be as low as 15\%.

This scheme, by the way, is essentially the same one that is used by the
IBM PL1 language.

    Process Structure

A process closure will be a frame, a pointer to a code vector, a saved
state, a queue of messages that have been sent to a process along with
possible return addresses for those messages, and a list of cleanup forms
to execute if the processes is killed.  The cleanup forms are executed
while the processes are not killable, which guarantees that the cleanup
forms get executed.

    Locking Primitives

Qlisp will need to implement the ability to exclude other processes
from using given resources. A simple spin lock based on test-and-set will
be sufficient for this, though test-and-add would be better. From this Qlisp
will provide a simple lock mechanism and perhaps a semaphore mechanism at
user level.

    Interprocessor Interrupts

In order to implement CATCH/QCATCH/THROW it must be possible to examine
processes and to kill them. The general scheme is that there is a global
queue of processes that are, in principle, ready to run. A data structure is
built containing pointers to specific processes. These processes may be waiting
an available processor or else they are being executed. Certain actions by
other processes will require that these specified processes be interrupted
and killed.  The processes will not be killed immediately if there is some
cleanup code specified for them. That is, Qlisp requires that the
programmer be able to execute a process in such a way that certain actions,
like closing files, be done before the process is terminated.

Killing processes outright can be accomplished by scanning through the
data structure of processes to kill, determining which processes are
running, and to remove the non-running ones from the runnable queue and
interrupting the processors running the killable processes. 

To implement this requires that the hardware support processor-to-processor
interrupts and that the operating system allows such interrupts and
can provide for user code being run when an interrupt occurs.

    Garbage Collection

Lucid will explore a variant of Halstead's garbage collection scheme, though
it is not anticipated that an incremental garbage collector will be
implemented. Most likely, a pure stop-and-copy garbage collector will
be implemented.

    Lisp Implementation

Lucid will use a deep-binding Common Lisp as the basis for Qlisp. The
Qlisp primitives will be runtime extensions to the basic Common Lisp.
The compiler will only know a very little amount about the Qlisp
primitives. The most important change that will be made to the Common Lisp
is to use the BBOF calling scheme rather than the relatively simple
stack scheme used on other machines we support.

Lucid will provide whatever debugging aids as prove useful for its own
debugging.  These aids will be relatively rudimentary, because the
development of sophisticated aids will depend on more extensive experience
with Qlisp.

    Lucid

Lucid implements Common Lisps on `stock' hardware. This is accomplished
using a native-code compiler, which compiles Common Lisp to the native
instruction set of the target machines.  Currently Lucid has implemented a
Common Lisp for MC68000-based computers running Unix
with virtual memory support. The Lisp system is
written to be portable, and there is little difficulty with porting it to
a NS32032-based computer running Unix with virtual memory support.

Lucid will use its portable Common Lisp as the basis for the Qlisp
implementation. Being a native-code Lisp, Qlisp will be a fairly
efficient implementation.

The work will take three years to complete and will be staged in such a
way that there will be a prototype Qlisp available approximately one year
after the start of work. During the first six months Lucid will port its
basic Common Lisp to the target computer; included in this will be the
change from a stack-based function-calling regime to the frame-based
regime.  During the second six months Lucid will do an initial
implementation of the bulk of the initial Qlisp system. This
implementation will only spawn a number of processes equal to the number
of processes. No garbage collector will be written. UNWIND-PROTECT will
also be omitted, because that feature requires the operating system to
support user-code running `uninterruptably' after an earlier interrupt.
The initial system will also not include much in the way of debugging aid
for multiprocessing, though the Lisp itself will be well-equipped in this
area.

The point of the initial implementation is to allow the Lucid Qlisp staff
and the Stanford project members
to begin using and critiquing the implementation. Of special interest
will be the initial benchmarking of Qlisp to determine performance
bottlenecks, so that improvements to the design and implementation
can be made.

The second year will be devoted to advancing the implementation to the
point where it represents a complete Qlisp. Full spawining capabilities,
full UNWIND-PROTECT, and those improvements to the language and the
implementation that are suggested by the initial user community and that
appear most important will be done. Lucid anticipates that this phase of
the work will require some amount of operating system work, possibly with
the co-operation of the hardware manufacturer's operating system or
software group.

The third year will concentrate on tuning the implementation and working
closely with the Stanford Qlisp project's technical staff to remove
performance bottlenecks, to improve debugging aids, and to improve the
definition of Qlisp.

At the end of the project the following will have been delivered:

1. A working Common Lisp system, provided as a single copy on magnetic tape,
in the form of object code executable on a uniprocessor version of the
multiprocessor.

2. A working Qlisp in the form of extensions to Common Lisp.  This shall
be a fully functioning Qlisp multiprocessor system.  The source code for
Qlisp aside from that covered in number 1 will be available for Stanford
use and modification. The object code for the Qlisp implementation will be
placed in the public domain, especially for use by other DARPA
contractors.

3. A set of working papers and other documents describing the implementation
of Qlisp will be written and published at least as part of the Stanford
report on the project and, it is hoped, in journals or presented at conferences.

In summary, Lucid considers the sources for the portable Common Lisp,
which are sold as the Lucid Portable Common Lisp Development Environment
and as the Lucid Portable Common Lisp Application Environment as
proprietary. Lucid considers all deliverables of the Qlisp project that
are additions to the source code kernel for these Portable Common Lisp
products and that implement Qlisp as public domain.  Lucid will retain the
right to use code developed during the project as commercial products.

    Lucid assurances to Stanford

Lucid acknowledges that the participation of Dr. Richard Gabriel is
essential to the implementation of Qlisp.  Lucid agees to notify the
Principal Investigator of the Qlisp project if Dr.~Gabriel is unable to
fulfill the minimum work level specified in the budget for a continuous
period of 60 days, such notification to be made within 5 working days of
this occurrence.  Lucid shall have 60 days from the date of notification
to the Principal Investigator of Dr.~Gabriel's inability to continue on
the project to notify the Principal Investigator of a replacement to
Dr.~Gabriel.  If the Principal Investigator approves the replacement,
Lucid shall have an additional 60 days (120 days cumulative) in which to
make Dr.~Gabriel's replacement available for Qlisp participation.

If Lucid is unable to meet these deadlines or the Principal Investigator
does not approve of the replacement for Dr. Gabriel, Stanford University
shall have as its sole remedy the right to terminate this contract, but
shall retain the right to use the Qlisp multiprocessor system to the
extent that it has been developed, including the Common Lisp object code,
Neither Stanford University nor Lucid shall have any obligation to the
other party after termination.  In the event of termination, Lucid shall
retain rights to its Licensed Software.

The Qlisp development and support staff at Stanford will have the right
to unlimited use of all Lucid Portable Common Lisp object code for work
in association with the Qlisp project.

Lucid agrees to keep an escrow account which contains all the source
code and documentation, including all updates and bug fixes to the
Lucid Portable Common Lisp products. In the event of a complete
termination of Lucid as a business, the Qlisp project will have the
non-exclusive rights to use the escrow contents for the sole purpose
of continuing the Qlisp project.

At Stanford's option, Lucid also agrees to maintain the software developed
under this contract for up to an additional three years beyond normal
termination of this contract.  The fees for this work would be the same as
for the third year of this proposal, adjusted for inflation.

In the event that Lucid is unable to perform due to its termination
as a business and Stanford is unable to gain access to the Lucid escrow
account, Stanford Qlisp research personnel shall have access to the
Lucid source code and docuumentation at Lucid's site.

     APPENDIX D -- Budget for eighteen months beginning 1 December 1985.

		Stanford University proposal to DARPA
				for
		    Qlisp on parallel processors

			     Budget for period     1          2
				    duration	1 year	   6 months
				    beginning	12-1-85    12-1-86
				    ending	11-30-86   5-31-87
Personnel
    Prof. John McCarthy, Principal Investigator	21,058      6,650
      (15% acad. yr., 50% summer)

    Lester Earnest, Senior Res. Assoc. (100%)	67,500     33,750

    Carolyn Talcott, Research Associate (100%)	43,000     21,500

    -----, Research Associate (100%)		41,000     20,500

    -----, Computer Systems Analyst (100%)	40,000     20,000

    -----, Computer Technician (25%)		 8,000	    4,000

    Ross Casley, Student Research Assistant	12,600      5,040
		(50% acad. yr., 100% summer)
    Ian Mason, Student Research Assistant	12,600      5,040
		(50% acad. yr., 100% summer)
    -----, Student Research Assistant			    5,040
		(50% acad. yr., 100% summer)
    -----, Student Research Assistant			    5,040
		(50% acad. yr., 100% summer)
    -----, Secretary (50% time)			10,440      5,220
					       -------    -------
	Salary subtotals		       256,198    131,780

	Allowance for salary increases (9%/yr)	     0     11,860
					       -------    -------
	Salary totals			       256,198    143,640

	Staff benefits (25.4% initially,	65,202     36,772
	  25.6% beg. 9/1/86)

    Consultants (10 days/yr. @ $500)		 5,000      2,500

    Travel (8 East Coast trips/yr. @ $1000,	15,000      7,600
	14 Western trips @ $500, adjusted for
	inflation)
    Computer maintenance 			73,819	   18,455
	(based on Sequent Computer)
    Computer time costs (based on 1984 usage	36,000     24,000
	of SAIL computer usage by principals)
    Other direct costs				22,600     13,000
					       -------    -------
	Subtotal			       471,164    245,967

    Capital equipment
      Multiprocessor computer system
	(e.g. Sequent Balance 8000 system)     307,580
      Ethernet workstation cluster (8 term.)    24,000
      Ethernet page printer			11,937
      Microwave link				30,000
      Additional workstations & peripherals		   12,000

    U.C. Berkeley subcontract		       182,000    102,481

    Lucid subcontract			       518,000	  204,600

    Indirect costs (69% of direct costs        340,873    179,556
      initially, 73% beginning 9/1/86,
      excluding all capital equipment and
      subcontract amounts over $25,000)	       -------    -------

    Total by period			     1,901,264    744,604
					       -------    -------
    Project cumulative total		     1,901,264  2,645,868

			U.C. Berkeley Budget

18 months beginning 12/1/85

A. Salaries & Wages 1)	 Period from	12-1-85		12-1-86
				to	11-30-86	5-31-87

No.  Position (Time)		Monthly	Total 

1  Professor (1 Mo. summer)	5356	$5,356	**
   Student Post Grad Res.
2	(1 Mo. @ 80%		1995	 3,192	+
	2 Mo. @ 80%		2109	 6,749	+
	4 Mo. @ 50%		2109	 8,436	++
	5 Mo. @ 50%)		2174	10,870	++
3	(6 Mo. @ 50%)		2337		++	21,033
1  Programmer 3 (1 Mo. @ 50%	2504	 1,252	*
	11 Mo. @ 50%)		2647	14,559	*
	(6 Mo. @ 50%)		2948		*	 8,844
1  Admin. Assist. I
	(1 Mo. @ 25%		1612	   403	*
	11 Mo. @ 25%)		1704	 4,686	*
	(6 Mo. @ 25%)		1815		*	 2,722
Var.   Clerical (12 Mo.)	 300	 3,600	*
		(6 Mo.)		 340			 2,040

	Total Salaries & Wages			$59,103		$34,639

1) All Salaries and Wages are based on current published University rates,
and include an estimated 5.7% range adjustment effective July 1,1985 then
a 7.5% for academic titles and a 6.5% for staff title on each July 1
thereafter.  Individual merit increases are included when applicable.
Academic titles include an additional 3.1% range adjustment effective
1/1/86, then a 7.5% for academic titles and a 6.5% for staff titles on
each July 1 thereafter.

B. Employee Benefits

28.25%	salaries marked *		$6,921		$3,844
19.78%	salaries marked **		 1,059		     0
1.43%	salaries marked +		   142		     0
.92%	salaries marked ++		   178		   194

	Total Employee Benefits			$8,300		$4,038

C.  Permanent Equipment

Qty	Description	Cost

1	Fujitsu Disk Drive		10,000
1	Fujitsu Disk Drive				10,000

	Total Equipment				$10,000		$10,000

D.  Travel

Domestic:  as follows, to participate in technical meetings related to
proposed research; Three round trips (Principal Investigator and two
studens to attend technical conference related to proposed research (e.g.
SYMSAC Conference 1986).  $800 air fare; four days per diem at $400;
registration fee $100; misc. and ground transportation - $50.

	Total Travel				$4,050		$2,025

E.  Supplies & Expense

  Sun Microsystems, Inc.		 5,000		 2,025
  In-house support groups		37,962		18,981
    based on 1,850 hours @ $20.52/hour.
  Expendable research supplies		3,530		 1,765
  Mailing, Telephone, Xerox, Office	1,500		   750

	Total Supplies & Expenses		$47,992		$23,521

F. Total Direct Costs				$129,445	$74,223

G.  Indirect Costs
  44% of Total Direct Costs excluding	 $52,555 		$28,258
  permanent equipment.

TOTAL COST OF RESEARCH PROGRAM			$182,000	$102,481
				Lucid
			Project Cost Estimate
			      ($000's)
					   Half-
				Year 1	   Year 2

Direct Labor (Sch. A)		 109.2	     56.7

Salary Related Expense @19.8%     21.6       11.2
				-----------------
Salary Expense			 130.8       67.9

Overhead @148%			 193.6      100.5

Other Direct Project Costs 
(Sch. B)			 126.0        9.5
				-----------------
			  	 450.4      177.9

Fee @15%			  67.6       26.7
				-----------------
Total Project Cost		 518.0	    204.6

Notes:
1.  Project cost assumes 1 Sequent machine provided to Lucid at no additional 
cost located at Lucid facilities for duration of project.

2.  Salary Related Expense and overhead are provisional rates based on FY86
(year end June 30) business plan projections.

3.  Direct Labor rates escalated at 10% per year.


			Schedule A
		       Direct Labor
			($000's)
					   Half-
				Year 1	   Year 2

Principal Investigator
	man-months		   3	      1
  	rate per month		   6.0        6.6
	total dollars		  18.0	      6.6

Senior Scientist
	man-months		  12	      6
	rate per month		   5.0        5.5
	total dollars		  60.0	     33.0

Scientist
	man-months		   6	      3
	rate per month		   4.2	      4.6
	total dollars		  25.2	     13.8

Technician
	man-months		   2	      1
	rate per month		   3.0	      3.3
	total dollars		   6.0	      3.3

Total Man-Months		  23	     11

Total Dollars			 109.2	     56.7


				Schedule B
			Other Direct Project Costs
				($000's)

					   Half-
				Year 1	   Year 2

Computer Equipment & Supplies      
	Symbolics 3670		   108	  
	Supplies @ 3K/yr	     3	        1.5
	Stanford Communication	     2          1

Travel & Subsistence
	Air		
	2 trips to Washington, D.C. @1.5 ea.
	1 trip to National Conference @1.5
	4 trips to East Coast, technical workshop @1.5 ea.

	Local travel @.5/yr	    11	       6
	 escalate @10%/yr

Printing and Reproduction @2K/yr     2	       1
       				 ---------------
Total			           126	       9.5
     APPENDIX D -- Budget for eighteen months beginning 1 December 1985.

		Stanford University proposal to DARPA
				for
		    Qlisp on parallel processors

[Recommended related work at University of California at Berkeley is not
included in this budget.]

			     Budget for period     1          2
				    duration	1 year	   6 months
				    beginning	12-1-85    12-1-86
				    ending	11-30-86   5-31-87
Personnel
    Prof. John McCarthy, Principal Investigator	21,058      6,650
      (15% acad. yr., 50% summer)

    Lester Earnest, Senior Res. Assoc. (100%)	67,500     33,750

    Carolyn Talcott, Research Associate (100%)	43,000     21,500

    -----, Research Associate (100%)		41,000     20,500

    -----, Computer Systems Analyst (100%)	40,000     20,000

    -----, Computer Technician (25%)		 8,000	    4,000

    Ross Casley, Student Research Assistant	12,600      5,040
		(50% acad. yr., 100% summer)
    Ian Mason, Student Research Assistant	12,600      5,040
		(50% acad. yr., 100% summer)
    -----, Student Research Assistant			    5,040
		(50% acad. yr., 100% summer)
    -----, Student Research Assistant			    5,040
		(50% acad. yr., 100% summer)
    -----, Secretary (50% time)			10,440      5,220
					       -------    -------
	Salary subtotals		       256,198    131,780

	Allowance for salary increases (9%/yr)	     0     11,860
					       -------    -------
	Salary totals			       256,198    143,640

	Staff benefits (25.4% initially,	65,202     36,772
	  25.6% beg. 9/1/86)

    Consultants (10 days/yr. @ $500)		 5,000      2,500

    Travel (8 East Coast trips/yr. @ $1000,	15,000      7,600
	14 Western trips @ $500, adjusted for
	inflation)
    Computer maintenance 			73,819	   18,455
	(based on Sequent Computer)
    Computer time costs (based on 1984 usage	36,000     24,000
	of SAIL computer by principals)
    Other direct costs				22,600     13,000
					       -------    -------
	Subtotal			       473,819    245,967
    Capital equipment
      Multiprocessor computer system
	(e.g. Sequent Balance 8000 system)     307,580
      Ethernet workstation cluster (8 term.)    24,000
      Ethernet page printer			11,937
      Microwave link				30,000
      Additional workstations & peripherals		   12,000

    Lucid subcontract			       518,000	  204,600

    Indirect costs (69% of direct costs        349,173    179,556
      initially, 73% beginning 9/1/86,
      excluding all capital equipment and
      subcontract amounts over $25,000)	       -------    -------

    Total by period			     1,714,509    642,123
					       -------    -------
    Project cumulative total		     1,714,509  2,356,632


				Lucid
			Project Cost Estimate
			      ($000's)
					   Half-
				Year 1	   Year 2

Direct Labor (Sch. A)		 109.2	     56.7

Salary Related Expense @19.8%     21.6       11.2
				-----------------
Salary Expense			 130.8       67.9

Overhead @148%			 193.6      100.5

Other Direct Project Costs 
(Sch. B)			 126.0        9.5
				-----------------
			  	 450.4      177.9

Fee @15%			  67.6       26.7
				-----------------
Total Project Cost		 518.0	    204.6

Notes:
1.  Project cost assumes 1 Sequent machine provided to Lucid at no additional 
cost located at Lucid facilities for duration of project.

2.  Salary Related Expense and overhead are provisional rates based on FY86
(year end June 30) business plan projections.

3.  Direct Labor rates escalated at 10% per year.


			Schedule A
		       Direct Labor
			($000's)
					   Half-
				Year 1	   Year 2

Principal Investigator
	man-months		   3	      1
  	rate per month		   6.0        6.6
	total dollars		  18.0	      6.6

Senior Scientist
	man-months		  12	      6
	rate per month		   5.0        5.5
	total dollars		  60.0	     33.0

Scientist
	man-months		   6	      3
	rate per month		   4.2	      4.6
	total dollars		  25.2	     13.8

Technician
	man-months		   2	      1
	rate per month		   3.0	      3.3
	total dollars		   6.0	      3.3

Total Man-Months		  23	     11

Total Dollars			 109.2	     56.7
Qlisp revised budget
Here is a revised budget covering the last half of FY86 and all of FY87.
As requested, it omits the parallel computer but includes other required
equipment and is squeezed down on several items.  As you can see, the
bottom line is $1,869,388 for the 18 month period.

I will contact Ike Nasssi as you suggest.  Given that whatever computer we
buy now will be a shared-use machine, that Sequent has been delivering
parallel systems longer than the competition, that their software seems to
work and that they enjoy a reputation for meeting commitments, there will
have to be strong reasons for choosing something other than the Sequent
machine.  I would be interested in whatever insights you may have on this
issue.

	Les Earnest

-------------------------------

     APPENDIX D -- Budget for eighteen months beginning 1 April 1986.

		Stanford University proposal to DARPA
				for
		    Qlisp on parallel processors

[Funds fo the required parallel computer are NOT included.]

Personnel
    Prof. John McCarthy, Principal Investigator	36,000
      (15% acad. yr., 50% summer)

    Lester Earnest, Senior Res. Assoc. (50%)	50,625

    Carolyn Talcott, Research Associate (100%)	64,500

    -----, Research Associate (100%)		61,500

    -----, Computer Systems Analyst (100%)	60,000

    -----, Computer Technician (25%)		12,000

    Ross Casley, Student Research Assistant	20,160
		(50% acad. yr., 100% summer)
    Ian Mason, Student Research Assistant	20,160
		(50% acad. yr., 100% summer)
    -----, Student Research Assistant		 7,560
	        (beg. 4/1/87; 50% acad. yr.,
		 100% summer)
    -----, Student Research Assistant		 7,560
	        (beg. 4/1/87; 50% acad. yr.,
		 100% summer)
    -----, Secretary (50% time)			15,660
					       -------
	Salary subtotals		       340,065

	Allowance for salary increases		22,104
		(9% beginning 9/1/86)
					       -------
	Salary totals			       362,169

	Staff benefits (25.6%)			92,715

    Consultants (10 days/yr. @ $500)		 7,500

    Travel (8 East Coast trips/yr. @ $1000,	22,500
	14 Western trips/yr. @ $500)
    Computer maintenance 			45,000

    Computer time costs				50,000

    Other direct costs				36,100
					       -------
	Subtotal			       615,984

    Capital equipment
      Ethernet workstation cluster (8 term.)    24,000
      Ethernet page printer			11,937
      Microwave link				30,000
      Interfacing equipment & peripherals	12,000
					       -------
	Subtotal				77,937

    Lucid subcontract			       722,600

    Indirect costs (69% of direct costs        460,869
      initially, 73% beginning 9/1/86,
      excluding all capital equipment and
      subcontract amounts over $25,000)	       -------

    Total				    $1,877,388

Qlisp Task Description
[Here is a proposed task description for the Qlisp project, which is to
be added to Contract N00039-84-C-0211, including a revised budget keyed
to a 1 June 1986 start.  I invite comments on any problems that you might
see.  Given that you already have a full proposal for this project, should
I put just the budget through the Stanford bureaucracy or should the text
of the task description also follow that route?  -Les]

An extension of Common Lisp for parallel processing, called Qlisp, is to
be developed using queue-based multi-processing, as described in Gabriel &
McCarthy, "Queue-based Multiprocessor Lisp" in Proceedings of the 1984 ACM
Symposium on Lisp and Functional Programming, August 1984.  It will have
the following features.

o   Each processor can address the whole of memory, and a processor may
    execute programs anywhere in memory on data located anywhere in memory.

o   The programmer indicates when parallelism is possible by using parallel
    constructions in the source language, which is an extension of Lisp.

o   When a program comes to a statement allowing parallelism and decides
    (according to the computed value of an allow-parallelism parameter
    in the statement) that parallelism is to be invoked, it adds a
    collection of tasks to a queue and starts on the first.

o   When a processor completes a task it goes to the queue for its next task.

Basing parallelism on run-time queues means that a program isn't written
or compiled for any specific number of processors.  The number available
can even change during the course of a computation.  Tasks need not be of
similar length, because a processor finishing a short task merely takes
another from the queue.

This task covers the first phase of an expected three year program,
involving a collaboration between Stanford University, and Lucid, Inc.
This task of 18 months duration will produce a functioning Qlisp system,
documentation and debugging tools at a cost of $1,943,464.  Assuming this
project starts on 1 June 1986, specific milestones are as follows.

1 Dec. 1986:  Have a monoprocessor version of a subset of Common Lisp suitable
	for parallel computation working on the chosen parallel computer.
	Preliminary specification of Qlisp extensions to Common Lisp completed.

1 June 1987:  Preliminary version of Qlisp working, with preliminary
	documentation.  Specification of test problems to be run will be complete.

30 Nov. 1987:  Improved version of Qlisp completed together with documentation.
	Test results of sample problems run on the parallel computer documented.

This is planned as a step toward the longer range goal of demonstrating
symbolic computation in a parallel computing system.


APPENDIX D -- Budget for 18 months from 1 June 1986 through 30 Nov. 1987

		Stanford University proposal to DARPA
				for
		    Qlisp on parallel processors

[Funds for the required parallel computer are NOT included.]

Personnel
    Prof. John McCarthy, Principal Investigator	35,467
      (15% acad. yr., 50% summer)

    Lester Earnest, Senior Res. Assoc. (50%)	50,625

    Carolyn Talcott, Research Associate (100%)	64,500

    -----, Research Associate (100%)		61,500

    -----, Computer Systems Analyst (100%)	60,000

    -----, Computer Technician (25%)		12,000

    Ian Mason, Student Research Assistant	20,160
		(50% acad. yr., 100% summer)
    -----, Student Research Assistant		20,160
		(50% acad. yr., 100% summer)
    -----, Student Research Assistant		 7,560
	        (beg. 6/1/87; 50% acad. yr.,
		 100% summer)
    -----, Student Research Assistant		 7,560
	        (beg. 6/1/87; 50% acad. yr.,
		 100% summer)
    -----, Secretary (50% time)			15,660
					       -------
	Salary subtotals		       355,192

	Allowance for salary increases		28,415
	  (8% beginning 9/1/86,
	   16% beginning 9/1/87)
					       -------
	Salary totals			       383,607

	Staff benefits (25.4% till 9/1/86,	98,459
	  25.6% till 9/1/87, then 26.2%)

    Consultants (10 days/yr. @ $500)		 7,500

    Travel (8 East Coast trips/yr. @ $1000,	22,500
	14 Western trips/yr. @ $500)
    Computer maintenance 			64,548

    Computer time costs				40,000

    Other direct costs				36,100
					       -------
	Subtotal			       652,714

    Capital equipment
      Ethernet workstation cluster (8 term.)    24,000
      Ethernet page printer			11,937
      Microwave link				30,000
      Interfacing equipment & peripherals	12,000
					       -------
	Subtotal				77,937

    Lucid subcontract			       722,600

    Indirect costs (69% of direct costs        490,213
      initially, 73% beginning 9/1/86,
      excluding all capital equipment and
      subcontract amounts over $25,000)	       -------

    Total				    $1,943,464


				Lucid
			Project Cost Estimate
			      ($000's)
					   Half-
				Year 1	   Year 2

Direct Labor (Sch. A)		 109.2	     56.7

Salary Related Expense @19.8%     21.6       11.2
				-----------------
Salary Expense			 130.8       67.9

Overhead @148%			 193.6      100.5

Other Direct Project Costs 
(Sch. B)			 126.0        9.5
				-----------------
			  	 450.4      177.9

Fee @15%			  67.6       26.7
				-----------------
Total Project Cost		 518.0	    204.6

Notes:
1.  Project cost assumes access to the selected parallel computer at Lucid
facilities provided to Lucid at no additional cost for duration of project.

2.  Salary Related Expense and overhead are provisional rates based on FY86
(year end June 30) business plan projections.

3.  Direct Labor rates escalated at 10% per year.


			Schedule A
		       Direct Labor
			($000's)
					   Half-
				Year 1	   Year 2

Principal Investigator
	man-months		   3	      1
  	rate per month		   6.0        6.6
	total dollars		  18.0	      6.6

Senior Scientist
	man-months		  12	      6
	rate per month		   5.0        5.5
	total dollars		  60.0	     33.0

Scientist
	man-months		   6	      3
	rate per month		   4.2	      4.6
	total dollars		  25.2	     13.8

Technician
	man-months		   2	      1
	rate per month		   3.0	      3.3
	total dollars		   6.0	      3.3

Total Man-Months		  23	     11

Total Dollars			 109.2	     56.7


				Schedule B
			Other Direct Project Costs
				($000's)

					   Half-
				Year 1	   Year 2

Computer Equipment & Supplies      
	Symbolics 3670		   108	  
	Supplies @ 3K/yr	     3	        1.5
	Stanford Communication	     2          1

Travel & Subsistence
	Air		
	2 trips to Washington, D.C. @1.5 ea.
	1 trip to National Conference @1.5
	4 trips to East Coast, technical workshop @1.5 ea.

	Local travel @.5/yr	    11	       6
	 escalate @10%/yr

Printing and Reproduction @2K/yr     2	       1
       				 ---------------
Total			           126	       9.5
Qlisp Task

	     John McCarthy, Professor of Computer Science
			Principal Investigator
BACKGROUND
 
     This research is for the implememntation and demonstration 
of applications of an extension of Lisp for parallel processing 
called Qlisp.  Qlisp allows the programmer to specify tasks that 
may be performed in parallel by creating queues of tasks.  This 
project involves developing Qlisp for a parallel processor, 
developing test applications for it, and testing the performance 
of the applications on substantial symbolic computation tasks.
 
     The project will be carried out with both formal and 
informal collaboration among several groups.  The principal investigator
for the overall project will be Professor John McCarthy.  The Qlisp
implementation shall be done under subcontract to Lucid, Inc.  The
implementation of Qlisp shall be supervised by Richard P. Gabriel of
Lucid.  Development of parallel programming tools and programs for testing
applications will be supervised by Carolyn Talcott.
 
     It is generally agreed that the main hope for large 
increases in computer speed, whether for numerical work or 
symbolic computation as in artificial intelligence, lies in 
massive parallelism.  Projects are being undertaken that will 
involve hundreds or even thousands of processors.  Therefore, it 
is important to explore a variety of approaches to getting good 
performance from parallel processors on a variety of problems.
 
     This project's approach is queue-based multi-processing.  It 
has the following features:
 
     Each processor can address the whole of memory, and a 
     processor may execute programs anywhere in memory on data located 
     anywhere in memory.
 
     The programmer indicates when parallelism is possible by 
     using parallel constructions in the source language, which is an 
     extension of Lisp.
 
     When a program comes to a statement allowing parallelism and 
     decides (according to the computed value of an allow-parallelism 
     parameter in the statement) that parallelism is to be invoked, it 
     adds a collection of tasks to a queue and starts on the first.
 
     When a processor completes a task it goes to the queue for 
     its next task.  It may execute some queue management code to 
     decide what to do next.
 
     Basing parallelism on run-time queues means that a program 
     isn't written or compiled for any specific number of processors.  
     The number available can even change during the course of a 
     computation.  Tasks need not be of similar length, because a 
     processor finishing a short task merely takes another queue. 
 
     It is necessary to follow through on the development and 
implementation of Qlisp by trying it out on substantial 
applications.  These trials will most likely lead to improvements 
in Qlisp and in the parallel processing hardware.  They may also 
determine whether it is possible to relax the requirement that 
all memory be equally accessible to all processors, since the 
hardware people find this expensive to implement.
 
     There are two kinds of problems to which parallelism can be 
applied.  In one case the goal is to make what you already have 
run faster.  This improves interaction with the computer and 
allows larger problems to be addressed.  In the second case, 
speed is of the esssence.  Part of the algorithm is devoted to 
insuring speed and some sort of real time behavior.  For example, 
a process may want to time out or use some default value if a 
subprocess does not reply within a given time limit.  Qlisp 
primitives directly address problems of the first sort.  
Additional primitives may be needed for the real time 
applications.
 
 
TOOLS FOR PARALLEL SYMBOLIC PROGRAMMING
 
     This work involves an entirely new style of programming and 
will require the development of new methods and tools to support 
the programming activity.  This development will be carried out 
in parallel with and in support of the chosen application.
 
Algorithm Design
 
     Part of the development of parallel Lisp involves 
discovering what primitives are needed to carry out various 
tasks.  This involves classifying problems as to the sort of 
parallelism required and the design of control structures 
appropriate for the various classifications.  Two well known 
classifications are AND versus OR parallelism and asynchronous 
tasks with occasional interactions versus synchronous tasks 
operating on a shared data structure.  Somewhat newer ideas 
include pipelines and other geometric structures that make it 
easy to visualize the interactions among a set of processes.  In 
some cases successful use of parallelism will require design of 
data structures with information making them suited to parallel 
processing.
 
Methods For Debugging
 
     Traditional Lisp debugging methods such as stepping and 
tracing are not going to be adequate for debugging Qlisp 
programs.  Programmers will need to learn where to look for bugs 
and to devise methods for identifying meaningful checkpoints.  
This effort shall include the building of tools for monitoring 
the progress of a set of processes working on a problem.  It 
shall also include work on informal methods of specification and 
reasoning about Qlisp programs as aids to the process of program 
development and testing.
 
 
Benchmarks and Measures of Success
 
     Benchmarks  for testing parallel Lisp and for comparing  the 
relative  efficiency of parallel and sequential algorithms  shall 
be designed.   Also tools for measuring factors such as degree of 
parallelism  achieved,  queue  management  overhead,  and  memory 
contention shall be developed.  Some measuring tools have already 
been   developed  by  Gabriel  in  a  sophisticated  system   for 
simulating execution of Qlisp programs.   This system was used in 
initial experiments testing Qlisp primitives.
 
 
MILESTONES
 
7 Months After Initiation of Task (MAIT) - Have a monoprocessor 
     version of a subset of Common Lisp suitable for parallel 
     computation working on a chosen parallel computer.  
     Preliminary specification of Qlisp extensions to Common Lisp 
     completed.
 
12 MAIT - Preliminary version of Qlisp working, with preliminary 
     documentation.  Specification of test problems to be run shall be 
     completed.
 
18 MAIT - Improved version of Qlisp completed together with 
     documentation.  Test results of sample problems run on the 
     parallel computer documented.
 
 
DELIVERABLES
 
12 MAIT - Copy of preliminary documentation.  
 
     Report detailing the specification of the test problems to 
     be run.
 
18 MAIT - Copy of documentation on the improved Qlisp.
 
     Report detailing test results of sample problems.
 
19 MAIT - Final report on task, including progress, lessons 
     learned, and future research to be considered.
 
In addition to the above stated milestones and deliverables, 
quarterly progress reports shall be submitted in accordance with 
DARPA/SPAWAR 613 reporting instructions.
 
 
 
BUDGET (18 months)

No capital equipment will be purchased without prior approval of DARPA.
 
Personnel
    Prof. John McCarthy, Principal Investigator 35,467
      (15% acad. yr., 50% summer)
 
    Lester Earnest, Senior Res. Assoc. (50%)    50,625
 
    Carolyn Talcott, Research Associate (100%)  64,500
 
    -----, Research Associate (100%)            61,500
 
    -----, Computer Systems Analyst (100%)      60,000
 
    -----, Computer Technician (25%)            12,000
 
    Ian Mason, Student Research Assistant       20,160
                (50% acad. yr., 100% summer)
    -----, Student Research Assistant           20,160
                (50% acad. yr., 100% summer)
    -----, Student Research Assistant            7,560
                (beg. 6/1/87; 50% acad. yr.,
                 100% summer)
    -----, Student Research Assistant            7,560
                (beg. 6/1/87; 50% acad. yr.,
                 100% summer)
    -----, Secretary (50% time)                 15,660
                                               -------
        Salary subtotals                       355,192

        Allowance for salary increases          28,415
          (8% beginning 9/1/86,
           16% beginning 9/1/87)
                                               -------
        Salary totals                          383,607
 
        Staff benefits (25.4% till 9/1/86,      97,053
          25.1% till 9/1/87, then 26.0%)
 
    Consultants (10 days/yr. @ $500)             7,500
 
    Travel (8 East Coast trips/yr. @ $1000,     22,500
        14 Western trips/yr. @ $500)
    Computer maintenance                        64,548
 
    Computer time costs                         40,000
 
    Other direct costs                          36,100
                                               -------
        Subtotal                               651,308
 
    Capital equipment
      4 Sun 3/50M-4 Workstations                22,120
      2 Fujitsu "Eagle" disk drives             15,600
      1 Alliant K002 cabinet			 7,500
      Interfacing equipment & peripherals        4,000
                                               -------
        Subtotal                                49,220
 
    Lucid subcontract                          722,600
 
    Indirect costs (69% of direct costs        489,196
      initially, 73% beginning 9/1/86,
      excluding all capital equipment and
      subcontract amounts over $25,000)        -------
 
    Total                                   $1,912,324

                                Lucid
                        Project Cost Estimate
                              ($000's)
                                           Half-
                                Year 1     Year 2
 
Direct Labor (Sch. A)            109.2       56.7
 
Salary Related Expense @19.8%     21.6       11.2
                                -----------------
Salary Expense                   130.8       67.9
 
Overhead @148%                   193.6      100.5
 
Other Direct Project Costs 
(Sch. B)                         126.0        9.5
                                -----------------
                                 450.4      177.9
 
Fee @15%                          67.6       26.7
                                -----------------
Total Project Cost               518.0      204.6
 
Notes:
1.  Project cost assumes access to Alliant machine provided to Lucid 
at no additional cost through a communication link to Lucid facilities
with a bidirectional transfer rate of at least 56 K bits/s. for duration 
of project.
 
2.  Salary Related Expense and overhead are provisional rates 
based on FY86 (year end June 30) business plan projections.
 
3.  Direct Labor rates escalated at 10% per year.
 
 
                        Schedule A
                       Direct Labor
                        ($000's)
                                           Half-
                                Year 1     Year 2
 
Principal Investigator
        man-months                 3          1
        rate per month             6.0        6.6
        total dollars             18.0        6.6
 
Senior Scientist
        man-months                12          6
        rate per month             5.0        5.5
        total dollars             60.0       33.0
 
Scientist
        man-months                 6          3
        rate per month             4.2        4.6
        total dollars             25.2       13.8
 
Technician
        man-months                 2          1
        rate per month             3.0        3.3
        total dollars              6.0        3.3
 
Total Man-Months                  23         11
 
Total Dollars                    109.2       56.7
 
 
                                Schedule B
                        Other Direct Project Costs
                                ($000's)
 
                                           Half-
                                Year 1     Year 2
 
Computer Equipment & Supplies      
        Symbolics 3670             108    
        Supplies @ 3K/yr             3          1.5
        Stanford Communication       2          1
 
Travel & Subsistence
        Air             
        2 trips to Washington, D.C. @1.5 ea.
        1 trip to National Conference @1.5
        4 trips to East Coast, technical workshop @1.5 ea.

        Local travel @.5/yr         11         6
         escalate @10%/yr
 
Printing and Reproduction @2K/yr     2         1
                                 ---------------
Total                              126         9.5